1. Field of the Invention
This invention relates to a method for compacting test sets for sequential circuits. More specifically, to a state relaxation based subsequence removal method for fast static compaction in sequential circuits.
This application relates to U.S. application Ser. No. 09/001,542 filed on Oct. 31, 1997 entitled, "Partitioning and Recording Methods for Static Test Sequence Compaction of Sequential Circuits," which is assigned to the Assignee of the present invention and which is incorporated herein by reference.
2. Background and Description of Related Art
Test application time (TAT) of sequential circuits is proportional to the number of test vectors in a test set and directly impacts the cost of testing. Thus, shorter test sequences are desired. Two types of compaction techniques exist: dynamic and static compaction. Dynamic techniques perform compaction concurrently with the test generation process and often require modification of the test generator. Static test sequence compaction, on the other hand, is a post-processing step after test generation. Static techniques are independent of the test generation algorithm and require no modification of the test generator. Even if dynamic compaction is performed during test generation, static compaction can further reduce the test set size obtained after test generation.
Several static compaction approaches for sequential circuits have been proposed in the following papers: Niermann, T. M., et al. "Test Compaction for Sequential Circuits," IEEE Trans. Computer-Aided Design, vol. 11, no. 2, pp. 260-67, February 1992, So, B., "Time-efficient Automatic Test Pattern Generation System," Ph.D. Thesis, EE Dept. Univ. of Wisconsin-Madison, 1994, Pomeranz, I., et al., "On Static Compaction of Test Sequences for Synchronous Sequential Circuits," Proc. Design Automation Conf., pp. 215-20, June 1996 and Hsiao, M. S. et al., "Fast Algorithms for Static Compaction of Sequential Circuit Test Vectors," Proc. IEEE VLSI Test Symp., pp. 188-195, April 1995.
Recent proposals include overlapping and reordering of test sequences obtained from targeting single faults to achieve compaction (Niermann and So). However, these approaches cannot be used on test sequences produced by random or simulation-based test generators.
Static compaction based on vector insertion, omission, or selection has also been investigated (Pomeranz). These methods require multiple fault simulation passes. They eliminate vectors from a test set without reducing the fault coverage that can be obtained using the original test set. When a vector is to be omitted or swapped, the fault simulator is invoked to make sure that the fault coverage is unaffected by the alteration to the test sequence. Very compact test sets can be achieved at the expense of prohibitively long execution times.
A fast static compaction technique for sequential circuits based on removing subsequences of test vectors was reported recently (Hsiao). This approach is based on two observations: (1) test sequences traverse through a small set of states that are frequently re-visited, and (2) subsequences corresponding to cycles may be removed from a test set under certain conditions. However, if test sets have few or no states that are re-visited, then the subsequence removal algorithm performs poorly. FIG. 1 is a table showing the number of vectors and states traversed by the HITEC test sets for some ISCAS89 benchmark circuits. Information regarding these test sets and circuits can be found in the following papers: Niermann, T. M., et al., "HITEC: A Test Generation Package for Sequential Circuits," Proc. European Conf. Design Automation (EDAC), pp. 214-18, 1991, Niermann, T. M., et al., "Method for Automatically Generating Test Vectors for Digital Integrated Circuits," U.S. Pat. No. 5,377,197, 1994, and Brglez, F., et al., "Combinational Profiles of Sequential Benchmark Circuits," Int. Symposium on Circuits and Systems," pp. 1929-34, 1989. Similar trends are seen in test sets generated by other test generators.